use std::collections::HashMap;

#[macro_export]
macro_rules! leetcode_vec {
    ($($x:expr),*) => {
        {
            let mut res = vec![];
            // 开始反复捕捉
            $(
                res.push($x.iter().map(|&s| s.to_string()).collect());
            )*
            res
        }
    };
}

// 332
fn find_itinerary(tickets: Vec<Vec<String>>) -> Vec<String> {
    let mut graph: HashMap<String, Vec<String>> = HashMap::new();
    for ticket in tickets.iter() {
        if let Some(edge) = graph.get_mut(&ticket[0]) {
            edge.push(ticket[1].to_string());
        } else {
            graph.insert(ticket[0].to_string(), vec![ticket[1].to_string()]);
        }
    }

    for (_, v) in graph.iter_mut() {
        v.sort();
    }

    // for (k, v) in graph.iter() {
    //     println!("{k} {:?}", v);
    // }
    // println!("{:?}", graph.get("JFK").unwrap());

    let mut res: Vec<String> = Vec::new();
    dfs_graph(&mut graph, "JFK".to_string(), &mut res);
    res.reverse();
    res
}

fn dfs_graph(graph: &mut HashMap<String, Vec<String>>, curr: String, res: &mut Vec<String>) {
    loop {
        if let Some(edges) = graph.get_mut(&curr) {
            if edges.len() == 0 {
                break;
            }
            let next = edges.remove(0);
            dfs_graph(graph, next, res);
        } else {
            break;
        }
    }
    res.push(curr);
}

// 普通解法
fn find_itinerar_dfs_shit(tickets: Vec<Vec<String>>) -> Vec<String> {
    let mut path: Vec<String> = Vec::new();
    let mut all_path: Vec<Vec<String>> = Vec::new();
    let mut used: Vec<bool> = vec![false; tickets.len()];
    let ticket_count = 0;
    // start from JFK
    path.push("JFK".to_string());
    // for (i, ticket) in tickets.iter().enumerate() {
    //     if ticket[0] == "JFK" {
    //         used[i] = true;
    //         break;
    //     }
    // }

    dfs(&tickets, &mut path, &mut used, ticket_count, &mut all_path);
    all_path.iter().min().unwrap().to_vec()
}

fn dfs(tickets: &Vec<Vec<String>>, path: &mut Vec<String>, used: &mut Vec<bool>, ticket_count: usize, all_path: &mut Vec<Vec<String>>) {
    if ticket_count == tickets.len() {
        all_path.push(path.clone());
        return;
    }
    for (i, ticket) in tickets.iter().enumerate() {
        if used[i] == true {
            continue;
        }
        if ticket[0] == *path.last().unwrap() {
            path.push(ticket[1].to_string());
            used[i] = true;
            dfs(tickets, path, used, ticket_count + 1, all_path);
            used[i] = false;
            path.pop();
        }
    }
}

#[test]
fn test_find_itinerary() {
    // let tickets = vec![vec!["JFK".to_string(),"SFO".to_string()],
    //                 vec!["JFK".to_string(),"ATL".to_string()],
    //                 vec!["SFO".to_string(),"ATL".to_string()],
    //                 vec!["ATL".to_string(),"JFK".to_string()],
    //                 vec!["ATL".to_string(),"SFO".to_string()]];

    // let tickets: Vec<Vec<String>> = leetcode_vec![["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]];
    let tickets: Vec<Vec<String>> = leetcode_vec![["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]];
    // println!("{:?}", tickets);
    // println!("{:?}", find_itinerar_dfs_shit(tickets));
    println!("{:?}", find_itinerary(tickets));
}